def longest_palindromic_subsequence(str):
    l = len(str)
    # dp = l+1 * l+1
    dp = [[0] * (l) for _ in range(l)]

    for i in reversed(range(l)):
        for j in range(i, l):
            if i == j:
                dp[i][j] = 1
            elif str[i] == str[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2 if i + 1 <= j - 1 else 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    return dp[0][l-1]

print(longest_palindromic_subsequence("bbbab"))
